1. Technical Field
The present invention relates in general to a method and system for manipulating raw isolines associated with a triangular mesh representing a surface and in particular to a method and system for smoothing isolines associated with a triangular mesh to provide an isoline map. In the most representative application of the present invention, the surfaces are topographical and the isolines are called contours.
2. Description of the Related Art
Topographic surfaces are the visible sections of the Earth modelled from the reality by people, such as civil engineers, surveyors, cartographers, and Earth scientists. Today, these surfaces are modelled on computers, manipulated with algorithms and graphics systems, and analyzed in many different ways. In many computer applications, a topographic surface is usually represented by a uniform grid--much like a fishnet spread over the land or as a "triangulation" or "triangular mesh", which is a set of triangular facets covering a surface without overlapping each other (except for the case in which one area is made to overhang another).
An example of a triangulation or a triangular mesh is found in FIG. 1, which depicts a small section of such a triangulation or triangular mesh representing a topographic surface. Depending on the application, triangulations may have any number of elements, which may range, for example, from a few dozen to several millions.
Contouring is probably the most frequent of the many operations that may be performed on a triangulation. When applied to a topographic surface, the result of a contouring operation is a contour map. "Contours" are lines of constant height. Examples of contours may be seen in FIG. 2, which is an illustration of the triangulation or triangular mesh depicted in FIG. 1 with raw contours added. A more general term for contours is "isolines", which is a concept that has found acceptance in almost any scientific and technical discipline. In this disclosure, "isolines" or simply "lines" are indistinctly utilized. Maps of isolines are the preferred illustration in the analysis of geologic, climatic, magnetic, gravitational, etc., phenomena. In this more general context, isolines are lines of constant field value.
Referring again to FIG. 2, there is an example of the simplest form of an isoline map. The isolines are "raw" isolines, having highly angular successions of more or less short segments that change direction at the triangle edges. The greatest value of raw isolines, in this case raw contours, for surveyors and civil engineers, and other users concerned with representation accuracy, is the fidelity with which they honor or conform with the source data from which the contours are derived. In addition, raw isolines are an attractive proposition to both programmers and system managers because of the simplicity of the algorithms involved. Programs for raw isolines are easy to write and maps may be completed in a relatively short time.
Although isolines are frequently used to represent types of surface other than topographical, they are almost exclusively utilized for uniform functions of two variables, also called single-value functions and scalar and potential fields. A uniform function is one which yields a single value f for each coordinate pair x, y. For topographic surfaces, f represents the height of the surface. In this description, these surfaces are called "single valued surfaces."
Notwithstanding the simplicity and time efficiency involved with raw isolines, many users tend to reject maps containing only raw isolines, preferring isoline maps with a more natural look, maps in which the broken lines have been smoothed into curves resembling the product of traditional cartographers.
The objection to raw isolines is not grounded on esthetics only. Raw isolines, especially when densely packed, clearly show the underlying triangular structure from which they were derived. As a result, it is difficult for the user to ignore that structure when trying to understand the surface shape from raw isolines. On the other hand, smooth isolines help the user by effectively concealing the triangular structure underneath.
In an attempt to provide the smooth isolines desired by many users, two fundamentally different approaches have been utilized. The first approach, line interpolation, totally ignores the triangles in the triangulation or triangular mesh. The source data for this first approach are the raw isolines within the triangular mesh, or in a broader sense, any other type of broken lines. The lines are transformed into curves, one piece at a time, that blend smoothly into each other. The conversion of the raw isolines involves inserting extra points between the vertices of the raw isolines, computed by means of equations of different types. The sequence of extra points define the smoothed isoline.
In the second method, patch contouring, the raw isolines are ignored. This approach consists of fitting patches of curved surfaces over each triangle in a triangulation or triangular mesh. The patches on adjacent triangles are forced to blend more or less continuously into each other. The contouring proceeds on the patches rather than on the original triangles. Because the patches are curved, the resulting isolines are also curved.
Several problems exist with utilizing a line interpolation approach. First, the smoothed isolines generally do not accurately correspond to the original data points because the triangulated surface is not considered during the operation. The smoothed isolines may only correspond to the vertices of the raw isolines under a line interpolation approach.
Next, in the smoothing of one isoline, the other isolines are ignored under the line interpolation approach. This method may lead to the isoline being smoothed intersecting its neighbors. Such intersections are generally unacceptable, since two different function values (two heights in topographic maps) at the point of intersection would occur.
In attempting to avoid the crossing of isolines, designers have often resorted to equations of degrees higher than quadratic. The penalty associated with this solution is usually an introduction of "fantasies" in the smoothed lines. "Fantasies" are undulations in the lines unwarranted by the source data. The higher the degree, the higher the potential for fantastic curves, which are curves containing fantasies. FIG. 3A depicts a section of the area shown in FIG. 1 and FIG. 2 with the isolines smoothed with a fifth degree line interpolation program. In addition to the undesirable effect of introducing fantasies, raising the degree in the curves above the quadratic also greatly increases program complexity, execution time, and computer storage requirements.
Another inadequacy is the fact that in addition to isolines, other means of rendering surfaces exist, such as, for example, profiles or fishnets in perspective views of different geometries, and maps colored in continuous tones. Presently, no available commercial packages exist to smooth the surfaces, either for perspective views or for continuous tone maps, in a way consistent with the results of the line interpolation approach.
The patch contouring approach, like the line interpolation approach, also presents problems in smoothing isolines. The mathematics of rigorously fitting patches to any triangulation, without adopting unnatural shapes, is anything but elementary, and the design of algorithms is then anything but simple. Compared to what the raw isoline approach needs, the number of operations per triangle and isoline are enormous. Processing times are larger in the same ratio, and for dense isoline maps, processing times may be exorbitant. Data processing systems processing dozens of isoline maps per day are not uncommon. In such data processing systems, a complex smoothing procedure may not be acceptable. Any attempt to significantly reduce processing time requires large amounts of storage space. For example, the simplest patch fitting method requires a minimum storage of 12 extra coefficients per vertex, plus three coefficients per triangle, all of which quadruples the basic data storage requirements for raw contouring.
Furthermore, compared to the operation on flat triangles, the contouring of curved patches is a very complex task. In contouring awkward triangle configurations, frequently found in topographic applications, the patches may be forced to adopt convoluted shapes. The patches are the result of very complex expressions and may have more than a single local maximum or minimum. Then, if used directly and not as an intermediate data structure-as is explained next-, the patches will have to be exhaustively scanned in order to "thread" through them all possible isolines. In fact, this direct procedure is seldom, if ever, implemented in commercial packages. Instead, the patches are utilized to define an orthogonal grid of z-values at regular intervals on the x,y plane. This grid is then contoured, usually with programs specific for grids. The price, in terms of processing resources, demanded by this kind of contouring is proportional to the square of the number of grid elements, which must be added to the cost of the lengthy patch determination. All things considered, smooth patches and their contouring is a very costly exercise.
Furthermore, contouring by means of an intermediate grid may result on misrepresentations of the surface. Contrary to what happens in directly contouring a triangulation, the contouring of these grids does not necessarily ensure that all the features in the smoothed surfaces are shown in the resulting map: features smaller than the grid interval may be ignored. A consequence of this shortcoming is that the original data points, unless they coincide with grid intersections, may not be exactly honored by the grid isolines. Not surprisingly, very few commercial products for the Earth Sciences offers this kind of smoothing capability.
In the case of topographic mapping, the obstacles to the smoothing of isolines mentioned above are compounded by an additional requirement. Today's users prefer to establish some distinctions among the edges of the triangulation, which later, at contouring time, should translate as variable degrees of smoothing along different segments of the same contour. For example, a contour should not be smoothed at or near a retention wall. A contour crossing a glacial valley (with rounded shaped floor) should be smoothed to a higher degree than the contour crossing a mountain river valley (with a v-shaped floor). Similar considerations can be made in connection with geologic mapping and the existence of surface or subsurface discontinuities, such as faults.
Therefore, it would be desirable to have a method and a system for accurately smoothing raw isolines within a triangular mesh without the shortcomings of the two approaches described above.